//给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [1,2,3,4,5], k = 2
//输出：[4,5,1,2,3]
// 
//
// 示例 2： 
//
// 
//输入：head = [0,1,2], k = 4
//输出：[2,0,1]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 500] 内 
// -100 <= Node.val <= 100 
// 0 <= k <= 2 * 109 
// 
// Related Topics 链表 双指针 
// 👍 727 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution61 {
    /**
     * 解题思路：
     * 1.获取链表最大长度
     * 2.让链表首尾相连
     * 3.计算还需要移动的此处
     * 4.获取目标链表节点，然后将链表解除环状
     *
     * 解答成功:
     * 			执行耗时:0 ms,击败了100.00% 的Java用户
     * 			内存消耗:40.7 MB,击败了26.47% 的Java用户
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null) return head;

        // 辅助指针找length
        int len = 0;


        ListNode prev = new ListNode(0);
        prev.next = head;
        while (prev.next != null) {
            len++;
            prev = prev.next;
        }
        // 此时prev是指向最后一个节点，将链表成环
        prev.next = head;

        // 计算链表还需要移动的位置
        int move = len - (k%len);
        while(move != 0) {
            prev = prev.next;
            move--;
        }

        // 获得返回节点
        ListNode res = prev.next;
        // 链表解环
        prev.next = null;

        return res;
    }

    public static void main(String[] args) {
        new Solution61().rotateRight(new ListNode(1), 0);
    }
}
//leetcode submit region end(Prohibit modification and deletion)
